class Solution {
    public:
        int numTrees(int n) {
            //抽象出子问题：dp[i] 表示i个数有多少种二叉搜索树
            //当固定根节点为j时 dp【i】 = dp[j-1]*dp[i-j]
            vector<uint64_t> dp(n+1);
            dp[0] = 1;
            for(int i = 1 ; i < n+1 ; i++){
                for(int j = 1 ; j <= i ; j++){
                    dp[i] += dp[j-1]*dp[i-j];
                }
            }
            return dp[n];
        }
    };